Public announcement logic with distributed knowledge: expressivity, completeness and complexity
Identifieur interne : 001704 ( Main/Exploration ); précédent : 001703; suivant : 001705Public announcement logic with distributed knowledge: expressivity, completeness and complexity
Auteurs : Yì N. Wang [Norvège] ; Thomas Agotnes [Norvège]Source :
- Synthese : (Dordrecht) [ 0039-7857 ] ; 2013.
Descripteurs français
- Pascal (Inist)
English descriptors
- KwdEn :
Abstract
While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic (P AL) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. P AL extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on P ACD, the result of adding both common and distributed knowledge to P AL, which is more expressive than each of its component logics. We introduce an axiomatisation of P ACD, which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with S5 knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that P ACD is decidable, more precisely that it is EXPTIME-complete. This result also carries over to S5CD with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs.
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream PascalFrancis, to step Corpus: 000041
- to stream PascalFrancis, to step Curation: 000975
- to stream PascalFrancis, to step Checkpoint: 000050
- to stream Main, to step Merge: 001721
- to stream Main, to step Curation: 001704
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">Public announcement logic with distributed knowledge: expressivity, completeness and complexity</title><author><name sortKey="Wang, Yi N" sort="Wang, Yi N" uniqKey="Wang Y" first="Yì N." last="Wang">Yì N. Wang</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Computing, Mathematics and Physics, Bergen University College</s1><s2>Bergen</s2><s3>NOR</s3><sZ>1 aut.</sZ></inist:fA14><country>Norvège</country><wicri:noRegion>Bergen</wicri:noRegion></affiliation></author><author><name sortKey="Agotnes, Thomas" sort="Agotnes, Thomas" uniqKey="Agotnes T" first="Thomas" last="Agotnes">Thomas Agotnes</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Information Science and Media Studies, University of Bergen</s1><s2>Bergen</s2><s3>NOR</s3><sZ>2 aut.</sZ></inist:fA14><country>Norvège</country><wicri:noRegion>Bergen</wicri:noRegion></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">INIST</idno><idno type="inist">14-0052719</idno><date when="2013">2013</date><idno type="stanalyst">FRANCIS 14-0052719 INIST</idno><idno type="RBID">Francis:14-0052719</idno><idno type="wicri:Area/PascalFrancis/Corpus">000041</idno><idno type="wicri:Area/PascalFrancis/Curation">000975</idno><idno type="wicri:Area/PascalFrancis/Checkpoint">000050</idno><idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000050</idno><idno type="wicri:doubleKey">0039-7857:2013:Wang Y:public:announcement:logic</idno><idno type="wicri:Area/Main/Merge">001721</idno><idno type="wicri:Area/Main/Curation">001704</idno><idno type="wicri:Area/Main/Exploration">001704</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">Public announcement logic with distributed knowledge: expressivity, completeness and complexity</title><author><name sortKey="Wang, Yi N" sort="Wang, Yi N" uniqKey="Wang Y" first="Yì N." last="Wang">Yì N. Wang</name><affiliation wicri:level="1"><inist:fA14 i1="01"><s1>Department of Computing, Mathematics and Physics, Bergen University College</s1><s2>Bergen</s2><s3>NOR</s3><sZ>1 aut.</sZ></inist:fA14><country>Norvège</country><wicri:noRegion>Bergen</wicri:noRegion></affiliation></author><author><name sortKey="Agotnes, Thomas" sort="Agotnes, Thomas" uniqKey="Agotnes T" first="Thomas" last="Agotnes">Thomas Agotnes</name><affiliation wicri:level="1"><inist:fA14 i1="02"><s1>Department of Information Science and Media Studies, University of Bergen</s1><s2>Bergen</s2><s3>NOR</s3><sZ>2 aut.</sZ></inist:fA14><country>Norvège</country><wicri:noRegion>Bergen</wicri:noRegion></affiliation></author></analytic><series><title level="j" type="main">Synthese : (Dordrecht)</title><title level="j" type="abbreviated">Synthese : (Dordrecht)</title><idno type="ISSN">0039-7857</idno><imprint><date when="2013">2013</date></imprint></series></biblStruct></sourceDesc><seriesStmt><title level="j" type="main">Synthese : (Dordrecht)</title><title level="j" type="abbreviated">Synthese : (Dordrecht)</title><idno type="ISSN">0039-7857</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Knowledge theory</term></keywords><keywords scheme="Pascal" xml:lang="fr"><term>Théorie de la connaissance</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">While dynamic epistemic logics with common knowledge have been extensively studied, dynamic epistemic logics with distributed knowledge have so far received far less attention. In this paper we study extensions of public announcement logic (P AL) with distributed knowledge, in particular their expressivity, axiomatisations and complexity. P AL extended only with distributed knowledge is not more expressive than standard epistemic logic with distributed knowledge. Our focus is therefore on P ACD, the result of adding both common and distributed knowledge to P AL, which is more expressive than each of its component logics. We introduce an axiomatisation of P ACD, which is not surprising: it is the combination of well-known axioms. The completeness proof, however, is not trivial, and requires novel combinations and extensions of techniques for dealing with S5 knowledge, distributed knowledge, common knowledge and public announcements at the same time. We furthermore show that P ACD is decidable, more precisely that it is EXPTIME-complete. This result also carries over to S5CD with common and distributed knowledge operators for all coalitions (and not only the grand coalition). Finally, we propose a notion of a trans-bisimulation to generalise certain results and give deeper insight into the proofs.</div></front></TEI><affiliations><list><country><li>Norvège</li></country></list><tree><country name="Norvège"><noRegion><name sortKey="Wang, Yi N" sort="Wang, Yi N" uniqKey="Wang Y" first="Yì N." last="Wang">Yì N. Wang</name></noRegion><name sortKey="Agotnes, Thomas" sort="Agotnes, Thomas" uniqKey="Agotnes T" first="Thomas" last="Agotnes">Thomas Agotnes</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001704 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 001704 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= Francis:14-0052719
|texte= Public announcement logic with distributed knowledge: expressivity, completeness and complexity
}}
| This area was generated with Dilib version V0.6.33. |  |